﻿#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include "../Util/util.h"

using namespace std;

#define CHAR_MAX_LEN 0xff

class ScrambleStringTreeNode;

struct ScrambleStringProbChildren
{
	ScrambleStringTreeNode* left;
	ScrambleStringTreeNode* right;
};

class ScrambleStringTreeNode
{
public:
	ScrambleStringTreeNode(string value);
	void setValue(string value);
	string getValue();

public:
	vector<ScrambleStringProbChildren> probChildren;
	ScrambleStringTreeNode* parent;

private:
	string value;
};

ScrambleStringTreeNode::ScrambleStringTreeNode(string value)
{
	this->value = value;
	parent = nullptr;
}

void ScrambleStringTreeNode::setValue(string value)
{
	this->value = value;
}

string ScrambleStringTreeNode::getValue()
{
	return value;
}

/**
 * TODO: 如何构建出所有可能性的树?
 */
static void makeTrees(const char* str, ScrambleStringTreeNode** root, ScrambleStringTreeNode* parent)
{
	auto strLen = strlen(str);
	if (strLen == 1)
	{
		ScrambleStringTreeNode* node = new ScrambleStringTreeNode(str);
		if (!parent)
		{
			*root = node;
		}

		return;
	}

	if (!parent)
	{
		*root = new ScrambleStringTreeNode(str);
		parent = *root;
	}

	for (int i=0;i<strLen-1;i++)
	{
		char leftStr[CHAR_MAX_LEN] = { 0 };
		memcpy_s(leftStr, i + 1, str, i + 1);
		char rightStr[CHAR_MAX_LEN] = { 0 };
		memcpy_s(rightStr, strLen - i - 1, str + i + 1, strLen - i - 1);
		
		auto left = new ScrambleStringTreeNode(leftStr);
		auto right = new ScrambleStringTreeNode(rightStr);
		left->parent = parent;
		right->parent = parent;
		ScrambleStringProbChildren probChild = { left,right };
		parent->probChildren.push_back(probChild);
		makeTrees(leftStr, nullptr, left);
		makeTrees(rightStr, nullptr, right);
	}
}


static bool recurCheckScramble(const char* str1, const char* str2, const size_t strSize, int start1, int start2, int n)
{
	if (start1 + n > strSize || start2 + n > strSize) return false;

	if (n == 1)
	{
		return str1[start1] == str2[start2];
	}

	bool isScramble1;
	bool isScramble2;
	for (int i = 1; i < n; i++)
	{
		isScramble1 = recurCheckScramble(str1, str2, strSize, start1, start2, i);
		isScramble2 = recurCheckScramble(str1, str2, strSize, start1 + i, start2 + i, n - i);
		if (isScramble1 && isScramble2) return true;

		isScramble1 = recurCheckScramble(str1, str2, strSize, start1, start2 + n - i, i);
		isScramble2 = recurCheckScramble(str1, str2, strSize, start1 + i, start2, n - i);
		if (isScramble1 && isScramble2) return true;
	}

	return false;
}

static bool recurCheckScrambleDp(const char* str1, const char* str2)
{
	auto strSize = strlen(str1);
	int xSize = strSize;
	int ySize = strSize;
	int zSize = strSize + 1;
	//dp[x,y,z]=dp[x+y*xSize+z*xSize*ySize]

	bool* dp = (bool*)malloc(xSize * ySize * zSize * sizeof(bool));
	memset(dp, 0, xSize * ySize * zSize * sizeof(bool));

	// n==1
	for (int x = 0; x < xSize; x++)
	{
		for (int y = 0; y < ySize; y++)
		{
			dp[x + y * xSize + xSize * ySize] = str1[x] == str2[y];
		}
	}

	// n>1
	bool isScramble1;
	bool isScramble2;
	for (int n = 2; n < zSize; n++)
	{
		for (int start2 = strSize - n; start2 >= 0; start2--)
		{
			for (int start1 = strSize - n; start1 >= 0; start1--)
			{
				for (int i = 1; i < n; i++)
				{
					isScramble1 = dp[start1 + start2 * xSize + i * xSize * ySize];
					isScramble2 = dp[start1 + i + (start2 + i) * xSize + (n - i) * xSize * ySize];
					if (isScramble1 && isScramble2)
					{
						dp[start1 + start2 * xSize + n * xSize * ySize] = true;
						break;
					}

					isScramble1 = dp[start1 + (start2 + n - i) * xSize + i * xSize * ySize];
					isScramble2 = dp[start1 + i + start2 * xSize + (n - i) * xSize * ySize];
					if (isScramble1 && isScramble2)
					{
						dp[start1 + start2 * xSize + n * xSize * ySize] = true;
						break;
					}
				}
			}
		}
	}

	bool res = dp[strSize * xSize * ySize];
	free(dp);
	return res;
}

static bool areScrambleEachOther(const char* str1, const char* str2)
{
	if (!str1 || !str2) return false;

	auto str1Len = strlen(str1);
	auto str2Len = strlen(str2);
	if (str1Len != str2Len) return false;

	if (strcmp(str1, str2) == 0) return true;

	unordered_map<char, int> character1Map;
	unordered_map<char, int> character2Map;
	char cur;
	for (int i = 0; i < str1Len; i++)
	{
		cur = str1[i];
		character1Map[cur]++;
	}

	for (int i = 0; i < str2Len; i++)
	{
		cur = str2[i];
		character2Map[cur]++;
	}

	if (character1Map.size() != character2Map.size()) return false;

	int count;
	for (auto pairIt=character1Map.begin();pairIt!=character1Map.end();pairIt++)
	{
		cur = pairIt->first;
		count = pairIt->second;
		if (count != character2Map[cur])
			return false;
	}

	//return recurCheckScramble(str1, str2, str1Len, 0, 0, str1Len);
	return recurCheckScrambleDp(str1, str2);
}

/**
 * 一个字符串可以分解成多种二叉树结构。如果str长度是1，认为不可分解。如果str长度是N(N>1), 左部分长度可以是1~N-1, 剩下的是右部分的长度。左部分和右部分都可以按照同样的逻辑继续分解。形成的所有结构都是str的二叉树结构。
 * 比如，字符串"abcd", 可以分解为以下五种结构，
 *                       abcd
 *                  /           \
 *                 a            bcd
 *                          /           \
 *                         b            cd
 *                                     /   \
 *                                    c     d
 * 
 *                       abcd
 *                  /           \
 *                 a            bcd
 *                          /           \
 *                         bc            d
 *                       /    \          
 *                      b      c      

                        abcd
		         /                 \
				ab                 cd
			 /     \              /   \
			a       b            c     d


			            abcd
		        /                   \
			   abc                   d
			/       \
		   ab        c
		 /   \
		a     b

		                abcd
					/           \
				  abc            d
				/     \
			   a      bc
			         /  \
					b    c


 * 二叉树的任何一个兄弟组，可以选择交换顺序或不交换，然后提交到父节点；在上一层的兄弟组，还是可以交换顺序或不交换，再往上提交...
 * 
 * 比如:
 *                           abcd
 *                          /     \
 *                         a      bcd          交换顺序       cbd|a
 *                               /   \
 *                              bc    d        不交换顺序      cb|d
 *                             /  \
 *                            b    c           交换顺序        c|b
 * 
 * 形成的新字符串:cbda, 与原字符串"abcd"互为旋变串.
 * 
 * 思路：
 * 动态规划范围尝试。
 * str1从L开始N个字符，和str2从L1开始N个字符，是否互为旋变串?
 * 为什么不是设str1从L到R，和str2从L1到R1是否互为旋变串？因为这样的话会用到4个参数，dp表会非常庞大，但是上面的尝试方式只需要3个参数，那么3维dp表就搞定了。
 * 可能性按照第一刀怎么切分类。
 * 
 * str1: a1 a2 a3 a4 a5
 * str2: b1 b2 b3 b4 b5
 * 当N==1时，只要ak==bk, 就互为旋变串;
 * 当N==5时，
 * 第1种切法, a1|a2~a5, 这个时候，如果a1和b1互为旋变串，a2~a5和b2~b5互为旋变串, 则整体就互为旋变串; 如果a1和b5互为旋变串，a2~a5和b1~b4互为旋变串，则整体也互为旋变串。如果方才提到的两种组合都不互为旋变串，则尝试第2种切法.
 * 第2种切法, a1~a2|a3~a5, 这个时候，如果a1~a2和b1~b2互为旋变串，a3~a5和b3~b5互为旋变串；如果a1~a2和b4~b5互为旋变串，a3~a5和b1~b3互为旋变串，则整体也互为旋变串。如果方才提到的两种组合都不互为旋变串，则尝试第3种切法...
 * 第3种切法, 试a1~a3|a4~a5,如果不互为旋变串，试第4种切法。
 * 第4种切法，试a1~a4|a5, 如果还不行，则整体不互为旋变串。
 */
int main_scrambleString()
{
	char str1[] = "abcd";
	unordered_set<string> strSet;
	getFullPermutationOfCharacters(str1, strSet);

	const char* str2;
	for (auto strIt = strSet.begin(); strIt != strSet.end(); strIt++)
	{
		str2 = strIt->c_str();
		bool res = areScrambleEachOther(str1, str2);
	    printf("\"%s\" and \"%s\" are scramble each other: %d\n", str1, str2, res);
	}
	
	return 0;
}